package org.ala.linshen.dp;

/**
 * 给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。
 *
 * 请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。
 *
 * 如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[1,1],[3,4]]
 * 输出：8
 * 解释：严格递增路径包括：
 * - 长度为 1 的路径：[1]，[1]，[3]，[4] 。
 * - 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
 * - 长度为 3 的路径：[1 -> 3 -> 4] 。
 * 路径数目为 4 + 3 + 1 = 8 。
 * 示例 2：
 *
 * 输入：grid = [[1],[2]]
 * 输出：3
 * 解释：严格递增路径包括：
 * - 长度为 1 的路径：[1]，[2] 。
 * - 长度为 2 的路径：[1 -> 2] 。
 * 路径数目为 2 + 1 = 3 。
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 1000
 * 1 <= m * n <= 105
 * 1 <= grid[i][j] <= 105
 *
 * @author ala
 * @date 2024-09-23 16:01
 */
public class Q2328 {

    public static void main(String[] args) {
        Q2328 q = new Q2328();

//        int[][] grid = {{1,1},{3,4}};
        int[][] grid = {{1},{2}};

        System.out.println(q.countPaths(grid));
    }

    /**
     *  1）dp[i][j]表示能走到(i,j)点的方案数
     *      如果 grid[_i][_j] 比 grid[i][j] 小，则 dp[i][j] = dp[_i][_j]
     *  2）如果 grid[_i][_j] 比 grid[i][j] 小，则(i,j)点的入度+1
     *      从入度为0的点开始遍历
     *      如果遍历到的(i,j)，其上下左右存在比他大的点，则该点的入度-1
     *      若某个点的入度 == 0，则该点加入待遍历队列
     */
    public int countPaths(int[][] grid) {
        int M = grid.length, N = grid[0].length;

        // 统计入度，记录入度为0的点
        int[][] ins = new int[M][N];
        int[][] queue = new int[M * N][2];
        int ql = 0, qr = -1, qs = 0;
        int[][] dp = new int[M][N];
        for (int i = 0 ; i < M ; i++) {
            for (int j = 0 ; j < N ; j++) {
                for (int[] p : POINTS) {
                    int _i = i + p[0], _j = j + p[1];
                    if (_i < 0 || _i == M || _j < 0 || _j == N || grid[_i][_j] >= grid[i][j]) {
                        continue;
                    }
                    ins[i][j]++;
                }
                if (ins[i][j] == 0) {
                    queue[++qr] = new int[] {i, j};
                    qs++;
                }
            }
        }

        //  从入度为0的点开始遍历
        int res = 0;
        while (qs > 0) {
            int _ql = ql, _qr = qr;
            qs -= qr - ql + 1;
            ql = qr + 1;
            while (_ql <= _qr) {
                int[] r = queue[_ql++];
                int i = r[0], j = r[1], v = grid[r[0]][r[1]];
                dp[i][j] = 1;
                for (int[] p : POINTS) {
                    int _i = i + p[0], _j = j + p[1];
                    if (_i < 0 || _i == M || _j < 0 || _j == N) {continue;}
                    int _v = grid[_i][_j];

                    if (_v < v) {
                        dp[i][j] += dp[_i][_j];
                    }
                    if (_v > v && --ins[_i][_j] == 0) {
                        queue[++qr] = new int[] {_i, _j};
                        qs++;
                    }
                }
                res = (res + dp[i][j]) % MOD;
            }
        }
        return res;
    }
    static int[][] POINTS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int MOD = (int)1e9 + 7;
}
